import java.util.PriorityQueue;

public class SortList {
    // leetcode 排序链表
    // https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked
    public ListNode sortList(ListNode head) {
        // 建小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2)
                -> o1.val - o2.val);
        ListNode tmp = head;
        while (tmp != null) {
            queue.offer(tmp);
            tmp = tmp.next;
        }
        ListNode newHead = new ListNode();
        ListNode cur = queue.poll();
        newHead.next = cur;
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        if (cur != null) cur.next = null;
        return newHead.next;
    }

    /**
     * 归并排序
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        // 归并排序
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode l1 = mergeSort(head);
        ListNode l2 = mergeSort(slow);
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) cur.next = l1;
        if (l2 != null) cur.next = l2;
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode A = new ListNode(4);
        ListNode B = new ListNode(2);
        ListNode C = new ListNode(1);
        ListNode D = new ListNode(3);
        A.next = B;
        B.next = C;
        C.next = D;
        SortList sortList = new SortList();
        ListNode head = sortList.sortList(A);
        System.out.println(666);
    }
}
